package bfs;

import java.lang.foreign.AddressLayout;
import java.util.ArrayList;
import java.util.EnumSet;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class 火星词典 {
	Map<Character,Set<Character>> edges=new HashMap<>(); //统计字符的相邻边
	Map<Character, Integer> in=new HashMap<>();          //统计节点的入度
	boolean check;  //标记特殊情况
	public String alienOrder(String[] words) {
		//1.初始化入度哈希表+建图
		for(String s:words) {
			for(int i=0;i<s.length();i++) {
				char ch=s.charAt(i);
				in.put(ch, 0);
			}
		}
		int n=words.length;
		for(int i=0;i<n;i++) {
			for(int j=i+1;j<n;j++) {
				add(words[i],words[j]);
				if(check==true) return "";
			}
		}
		
		//拓扑排序
		Queue<Character> q=new LinkedList<>();
		StringBuffer ret=new StringBuffer();
		for(char ch:in.keySet()) {
			if(in.get(ch)==0) {
				q.add(ch);
			}
		}
		while(!q.isEmpty()) {
			char t=q.poll();
			ret.append(t);
			if(edges.containsKey(t)==false) {
				continue;
			}
			for(char ch:edges.get(t)) {
				in.put(ch, in.get(ch)-1);
				if(in.get(ch)==0) {
					q.add(ch);
				}
			}
		}
		//判断是否有环
		for(char ch:in.keySet()) {
			if(in.get(ch)!=0) {
				return "";
			}
		}
		return ret.toString();
	}    
	
	//收集两两字符的大小信息
	public void add(String s1,String s2) {
		int i=0;
		int n=Math.min(s1.length(), s2.length());
		for(;i<n;i++) {
			char c1=s1.charAt(i),c2=s2.charAt(i);
			//c1->c2
			if(c1!=c2) {
				if(edges.containsKey(c1)==false) {
					edges.put(c1, new HashSet<>());
				}
				if(edges.get(c1).contains(c2)==false) {
					edges.get(c1).add(c2);
					in.put(c2, in.get(c2)+1);
				}
				break;
			}
		}
		if(i==s2.length()&&i<s1.length()) {
			check=true;
		}
	}
}
